package main

import "math"

func main() {

	//root = [4,2,9,3,5,null,7]  深度3
	node3 := TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node4 := TreeNode{
		Val:   5,
		Left:  nil,
		Right: nil,
	}
	node5 := TreeNode{
		Val:   7,
		Left:  nil,
		Right: nil,
	}
	node1 := TreeNode{
		Val:   2,
		Left:  &node3,
		Right: &node4,
	}
	node2 := TreeNode{
		Val:   9,
		Left:  nil,
		Right: &node5,
	}
	root := TreeNode{
		Val:   4,
		Left:  &node1,
		Right: &node2,
	}

	//打印测试用例返回结果
	resp := minDepth(&root)
	println(resp)

}

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func minDepth(root *TreeNode) int {
	//边界检查：root为空节点
	if root == nil {
		return 0
	}
	//边界检查：root为叶结点
	if root.Left == nil && root.Right == nil {
		return 1
	}
	minD := math.MaxInt32 //声明一个中间变量
	//先拿到左子树的最小深度
	if root.Left != nil {
		minD = minDepth(root.Left)
	}
	//拿左子树的最小深度和右子树最小深度比较，谁更小谁就是最小深度
	if root.Right != nil {
		minD = min(minDepth(root.Right), minD)
	}
	return minD + 1 //最终该层的最小深度就是其子层的最小深度+1
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
